Contents

1. 1. 分析：

分析：

• 二叉树的遍历 + 同余定理

//版本一：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
#define MAXN 800010

int mod[MAXN];				//注意：用数组表示二叉树，则要求下标从1开始

int main(){

    int n, i;
    while(scanf("%d", &n) == 1 && n){
        mod[1] = 1;			//第一位等于1
        for(i = 2; mod[i - 1] != 0; i++)//从第二位开始,如果取模后等于0,则说明找到了
            mod[i] = (mod[i / 2] * 10 + i % 2) % n;//防止数据过大溢出，用同余定理取模
        i--;				//如果i是偶数则走向左孩子，否则走向右孩子
        int index = 0;
        while(i){			//找到了余数为0的二叉树的节点位置就逆向输出路径
            mod[index++] = i % 2;	//这个节点有对应的下标，取其二进制的最后一位
            i /= 2;//往上走一层       	//如果是偶数则说明是0,奇数说明是1
        }
        for(int i = index - 1; i >= 0; --i)
            printf("%d", mod[i]);	//逆向输出
        printf("\n");
    }
    return 0;
}

//版本二：用队列去做，其实意思差不多都是为了找到余数为0的节点
#include <cstdio>
#include <queue>
using namespace std;
bool ret[1000];
int ansz, retsz;
int main(int argc, char* argv[]){

    int n, t;
    while (scanf("%d", &n) == 1 && n)
    {
        queue<int> que;
        retsz = ansz = 0;
        que.push(1);
        while (1)
        {
            t = que.front();
            que.pop();
            ++ansz;
            if (t % n == 0)
                break;
            // 这里必须先0后1，因为这样才与奇偶对应
            que.push(t * 10 % n);
            que.push((t * 10 + 1) % n);
        }
        while (ansz)
        {
            ret[retsz++] = ansz & 1;//相当于%2，取二进制的最后一位
            ansz >>= 1;
        }
        for (int i = retsz - 1; i >= 0; --i)
            printf("%d", int(ret[i]));
        putchar('\n');
    }
    return 0;
}